package com.my.tree;

import java.util.*;
import java.util.function.Predicate;
import java.util.stream.Collectors;

/**
 * 构建树形结构的工具类
 * 该类负责从一个节点列表中构建出指定根节点的树形结构
 * 它通过递归方式构建每个节点的子节点，直到构建完整个树
 *
 * @param <T> 节点类型，必须继承自TreeNode
 */
public class TreeBuilder<T extends TreeNode<?>> {

    // 所有节点列表（已做拷贝，防止外部修改）
    private final List<T> nodes;

    // 根节点的判断条件
    private final Predicate<T> rootPredicate;

    // 节点排序比较器，可能为null
    private final Comparator<T> comparator;

    /**
     * 构造函数，初始化TreeBuilder
     *
     * @param nodes         节点列表，不能为空
     * @param rootPredicate 根节点的判断条件，不能为空
     * @param comparator    节点排序的比较器，可以为null
     */
    public TreeBuilder(List<T> nodes, Predicate<T> rootPredicate, Comparator<T> comparator) {
        this.nodes = new ArrayList<>(Objects.requireNonNull(nodes, "节点列表不能为空"));
        this.rootPredicate = Objects.requireNonNull(rootPredicate, "根节点判断条件不能为空");
        this.comparator = comparator;
    }

    /**
     * 构造函数，使用默认的根节点判断条件
     *
     * @param nodes         节点列表，不能为空
     * @param rootPredicate 根节点的判断条件，不能为空
     */
    public TreeBuilder(List<T> nodes, Predicate<T> rootPredicate) {
        this(nodes, rootPredicate, null);
    }

    /**
     * 构造函数，使用默认的根节点判断条件和默认的排序比较器
     *
     * @param nodes 节点列表，不能为空
     */
    public TreeBuilder(List<T> nodes) {
        this(nodes, (e) -> Objects.isNull(e.parentId()));
    }

    /**
     * 构造指定根节点的树
     *
     * @return 构造完成的树的根节点
     */
    public T build() {
        T rootNode = findRootNode();
        Set<T> nodeSet = new HashSet<>(nodes); // 使用 Set 提高查找效率
        buildIteratively(rootNode, nodeSet);
        return rootNode;
    }

    /**
     * 使用迭代方式构建树，避免递归导致的栈溢出
     *
     * @param rootNode 根节点
     * @param nodes    剩余未构建的节点集合
     */
    private void buildIteratively(T rootNode, Set<T> nodes) {
        // 使用队列来帮助迭代构建树结构
        Deque<T> queue = new ArrayDeque<>();
        queue.offer(rootNode);

        while (!queue.isEmpty()) {
            // 取出当前处理的节点
            T current = queue.poll();
            // 查找当前节点的所有子节点
            List<T> children = findChildNodes(current, nodes);

            // 如果存在比较器，则对子节点进行排序
            if (comparator != null) {
                children.sort(comparator);
            }

            // 创建并添加子节点列表到当前节点
            List<T> currentChildren = new ArrayList<>(children);
            current.addChildren(currentChildren);

            // 移除已构建的子节点，避免重复构建
            children.forEach(nodes::remove);
            // 将子节点加入队列，以迭代构建它们的子树
            queue.addAll(children);
        }
    }

    /**
     * 查找根节点
     *
     * @return 根节点
     * @throws IllegalArgumentException 如果找不到根节点或找到多个根节点
     */
    private T findRootNode() {
        List<T> rootNodes = nodes.stream().filter(rootPredicate).collect(Collectors.toList());

        if (rootNodes.isEmpty()) {
            throw new IllegalArgumentException("未找到根节点，无法构造树！");
        }
        if (rootNodes.size() > 1) {
            throw new IllegalArgumentException("找到多个根节点，无法构造树！");
        }
        return rootNodes.get(0);
    }

    /**
     * 查找指定节点的子节点
     *
     * @param pNode 父节点
     * @param nodes 节点集合
     * @return 子节点列表
     */
    private List<T> findChildNodes(T pNode, Set<T> nodes) {
        return nodes.stream()
                .filter(e -> Objects.equals(e.parentId(), pNode.nodeId()))
                .collect(Collectors.toList());
    }

}
